package com.leetcode.根据算法进行分类.滑动窗口相关;

/**
 * @author: ZhouBert
 * @date: 2021/2/23
 * @description: 1052. 爱生气的书店老板
 * https://leetcode-cn.com/problems/grumpy-bookstore-owner/
 */
public class B_1052_爱生气的书店老板 {


	/**
	 * 虽然官方题解的描述是使用高数来解决的。
	 * 但是感觉刷题过程下来，并没有必要使用高数来分析。
	 * --
	 * 这道题需要逆向考虑：
	 * 最多客户满意的数量 = 最多由原先生气 转为 不生气的 客户的数量（转换总和）
	 * 那么 ->
	 * 用 X 长的滑动窗口，获取最多的 转换总和
	 *
	 * @param customers
	 * @param grumpy
	 * @param X
	 * @return
	 */
	public int maxSatisfied(int[] customers, int[] grumpy, int X) {
		//1.为了便于分析，第一次遍历获取原始不生气的数量
		int len = customers.length;
		int sum = 0;
		if (X >= len) {
			//如果 X 大于总长度
			for (int i = 0; i < len; i++) {
				sum += customers[i];
			}
			return sum;
		}

		//此时 X< len
		for (int i = 0; i < len; i++) {
			if (grumpy[i] == 0) {
				sum += customers[i];
			}
		}
		//此时已经统计完毕本就不生气的满意客户数量
		int transSum = 0;
		int tMax = 0;
		// [)
		int left = 0, right = left + X;
		for (int i = 0; i < right; i++) {
			//统计转换的数量和
			if (grumpy[i] == 1) {
				transSum += customers[i];
			}
		}
		tMax = transSum;
		while (right < len) {
			if (grumpy[left] == 1) {
				//如果 left 处是 转换而来的，就要还回去
				transSum -= customers[left];
			}
			if (grumpy[right] == 1){
				transSum += customers[right];
			}
			tMax = Math.max(transSum, tMax);
			left++;
			right++;
		}
		return (sum + tMax);

	}
}
